package from_51_to_100;


import java.util.ArrayList;
import java.util.List;

/**
 * N后问题，1-N的排列，行列都不需要考虑，仅考虑斜线
 */
public class n皇后 {
    static int[] stack = new int[10]; // 状态位
    static int[] check = new int[10]; // 0: 未使用，1：使用
    static int top = 0;
    
    static List<List<Integer>> stacks = new ArrayList<>();
    static List<List<String>> arrayLists = new ArrayList<>();
    public static void main(String[] args) {
        for (int i = 0; i < 10 ; i++) {
            stack[i] = 0;
            check[i] = 0;
        }
        arrayLists.clear();
        fun3(5);
        fun4(stacks,5);
        System.out.println(arrayLists);
//        System.out.println("total: "+total);
    }
    public static void fun3(int N){ // 15皇后 ≈ 12000ms = 12s （12327、
        if(top == N){  // n 个元素里面选 r个元素。r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < N; i++) {
                list.add(stack[i]);
            }
            stacks.add(list);
            return;
        }
        for (int i = 1; i <= N; i++) {  // n 个元素
            if(top == 0){ // 第一行
                if(i > (N+1)/2)
                    continue;
            }
            if(check[i] == 0 ){ // r <= n, 原因：n=3时，且有check[i]的限制（3个元素都标记1后，递归不在执行），最多递归三次
                boolean i_isOk = true;
                if(top > 0){
                    for (int j = 0; j < top; j++) {
                        if(((top+i) == (j+stack[j]) || (top-i) == (j-stack[j]))){  // 列差：低    行差：高
                            i_isOk = false;
                            break;
                        }
                    }
                }
                if(i_isOk){
                    check[i] = 1;
                    stack[top++] = i;
                    fun3(N);
                    top--;
                    check[i] = 0;
                }
            }
        }
    }
    public static void fun4(List<List<Integer>> stacks, int n){
        System.out.println("stacks = " + stacks);
        if(n%2 == 0){
            for (int i = 0; i < stacks.size(); i++) {
                arrayLists.add(fun5(stacks.get(i), 0,n));
                arrayLists.add(fun5(stacks.get(i), 1,n));
            }
        }else {
            for (int i = 0; i < stacks.size(); i++) {
                List<Integer> list = stacks.get(i);
                if(list.get(0) <= (n+1)/2){
                    arrayLists.add(fun5(stacks.get(i), 0,n));
                    arrayLists.add(fun5(stacks.get(i), 1,n));
                }
                else
                    arrayLists.add(fun5(stacks.get(i), 0,n));
            }
        }
    }
    public static List<String> fun5(List<Integer> list,int flag,int n){
        List<String> lists = new ArrayList<>();
        if(flag == 0){
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i)+" ");
                char[] chars = new char[n];
                for (int j = 0; j < n; j++) {
                    if (j == list.get(i)-1)
                        chars[j] = 'Q';
                    else
                        chars[j] = '.';
                }
                lists.add(String.valueOf(chars));
            }
            System.out.println();
        }else {
            for (int i = list.size()-1; i >= 0; i--) {
                System.out.print(list.get(i)+" ");
                char[] chars = new char[n];
                for (int j = 0; j < n; j++) {
                    if (j == list.get(i)-1)
                        chars[j] = 'Q';
                    else
                        chars[j] = '.';
                }
                lists.add(String.valueOf(chars));
            }
            System.out.println();
        }
        return lists;
    }
}

